#include <stdio.h>

typedef int elem_type;

#define ELEM_SWAP(a, b) { register elem_type t = (a); (a) = (b); (b) = t; }

elem_type quick_select(elem_type arr[], int n)
{
    int low, high;
    int median;
    int middle, ll, hh;

    low = 0; high = n-1; median = (high + low)/2;

    for ( ; ; ) {
        if (high <= low) 
            return arr[median];
        
        if (high == low + 1) {
            if (arr[low] > arr[high]) 
                ELEM_SWAP(arr[low], arr[high]);
            
            return arr[median];
        }

        middle = (low + high)/2;
        if (arr[middle] > arr[high])           ELEM_SWAP(arr[middle], arr[high]);
        if (arr[low] > arr[high])              ELEM_SWAP(arr[low], arr[high]);
        if (arr[middle] > arr[low])            ELEM_SWAP(arr[middle], arr[low]);

        ELEM_SWAP(arr[middle], arr[low+1]);

        ll = low + 1;
        hh = high;
        for ( ; ; ) {
            do ll++; while (arr[low] > arr[ll]) ;
            do hh--; while (arr[low] < arr[hh]) ;
            
            if (hh < ll)
                break;
            ELEM_SWAP(arr[ll], arr[hh]);
        }
        ELEM_SWAP(arr[low], arr[hh]);
        
        if (hh <= median)
            low = ll;
        if (hh >= median)
            high = hh - 1;
    }
    
}
#undef ELEM_SWAP

int main(int argc, char *argv[])
{
    int a[] = {2, 3, 4, 6, 8, 1, 9};
    printf("median = %d\n", quick_select(a, sizeof(a)/sizeof(a[0])));

    return 0;
}
